package T76;

public class Main {
    public static void main(String[] args) {

    }
}

class Solution {
    public int maxSubArray(int[] nums) {
        int[] maxArr = new int[nums.length];
        maxArr[0] = nums[0];
        int max = nums[0];
        for(int i = 1; i < nums.length; i++) {
            maxArr[i] = Math.max(maxArr[i-1]+nums[i], nums[i]);
            max = Math.max(max, maxArr[i]);
        }
        return max;
    }
    public int maxSubArray1(int[] nums) {
        int pre = nums[0];
        int max = nums[0];
        for(int i = 1; i < nums.length; i++) {
            pre = Math.max(nums[i], pre+nums[i]);
            max = Math.max(pre, max);
        }
        return max;
    }
    static int left;
    static int right;

    static int sum;

    public static void extra(int[] nums) {
        int sum = Integer.MIN_VALUE;
        int pre = Integer.MIN_VALUE;
        int l = 0;
        for (int r = 0; r < nums.length; r++) {
            if(pre>=0) {
                pre += nums[r];
            }else {
                pre = nums[r];
                l = r;
            }
            if(pre>sum) {
                sum = pre;
                left = l;
                right = r;
            }
        }
    }
}
